package com.cn.algorithm.one.heap;


import com.cn.algorithm.one.printer.BinaryTreeInfo;
import com.cn.algorithm.one.printer.BinaryTrees;

import java.util.Comparator;

public class BinaryHeap<E> implements Heap<E> , BinaryTreeInfo {


    E[] elements;

    int size;

    public static final int DEFAULT_CAPACITY = 10;

    Comparator<E> comparator;

    public BinaryHeap(E[] arr, Comparator<E> comparator) {
        this.comparator = comparator;
        if (arr == null || arr.length == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            size = arr.length;
            elements = (E[]) new Object[size];
            for (int i = 0; i < size; i++) {
                elements[i] = arr[i];
            }
            heapify();
        }
    }

    public BinaryHeap(Comparator<E> comparator) {
        this(null, comparator);
    }

    public BinaryHeap(E[] arr) {
        this(arr, null);
    }

    public BinaryHeap() {
        this(null, null);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public E front() {
        return elements[0];
    }

    @Override
    public void add(E element) {
        checkCapacity(size + 1);
        elements[size++] = element;
        siftUp(size - 1);
    }

    @Override
    public E pop() {
        E oldElement = elements[0];
        elements[0] = elements[size - 1];
        elements[--size] = null;
        siftDown(0);
        return oldElement;
    }

    @Override
    public E replace(E element) {
        if (size == 0) {
            elements[size++] = element;
            return null;
        }
        E oldElement = elements[0];
        elements[0] = element;
        siftDown(0);
        return oldElement;
    }

    public void heapify() {
        for (int i = size / 2 - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    public void siftDown(int index) {
        E tmp = elements[index];
        int half = size / 2;
        while (index < half) {
            int left = index * 2 + 1;
            if ((left + 1) < size && compare(elements[left], elements[left + 1]) < 0) {
                left++;
            }
            if (compare(tmp, elements[left]) >= 0) {
                break;
            }
            elements[index] = elements[left];
            index = left;
        }
        elements[index] = tmp;
    }

    public void siftUp(int index) {
        E tmp = elements[index];
        while (index > 0) {
            int parent = (index - 1) >> 1;
            if (compare(tmp, elements[parent]) < 0) {
                break;
            }
            elements[index] = elements[parent];
            index = parent;
        }
        elements[index] = tmp;
    }

    public void checkCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (capacity <= oldCapacity) {
            return;
        }
        E[] oldElements = elements;
        elements = (E[]) new Object[oldCapacity + (oldCapacity >> 1 )];
        for (int i = 0; i < oldElements.length; i++) {
            elements[i] = oldElements[i];
        }
    }

    public int compare(E e1, E e2) {
        return comparator == null ? ((Comparable<E>) e1).compareTo(e2) : comparator.compare(e1, e2);
    }

    @Override
    public Object root() {
        return 0;
    }

    @Override
    public Object left(Object node) {
        int index = ((int)node << 1) + 1;
        return index >= size ? null : index;
    }

    @Override
    public Object right(Object node) {
        int index = ((int)node << 1) + 2;
        return index >= size ? null : index;
    }

    @Override
    public Object string(Object node) {
        return elements[(int)node];
    }

    public static void main(String[] args) {
        test2();
    }


    static void test1() {
        BinaryHeap<Integer> heap = new BinaryHeap<>();
        heap.add(68);
        heap.add(72);
        heap.add(43);
        heap.add(50);
        heap.add(38);
        heap.add(10);
        heap.add(90);
        heap.add(65);
        BinaryTrees.println(heap);
        // heap.remove();
        // BinaryTrees.println(heap);

        System.out.println(heap.replace(70));
        BinaryTrees.println(heap);
    }

    static void test2() {
        Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
        BinaryHeap<Integer> heap = new BinaryHeap<>(data);
        BinaryTrees.println(heap);

        data[0] = 10;
        data[1] = 20;
        BinaryTrees.println(heap);
    }

    static void test4() {
        // 新建一个小顶堆
        BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        // 找出最大的前k个数
        int k = 3;
        Integer[] data = {51, 30, 39, 92, 74, 25, 16, 93,
                91, 19, 54, 47, 73, 62, 76, 63, 35, 18,
                90, 6, 65, 49, 3, 26, 61, 21, 48};
        for (int i = 0; i < data.length; i++) {
            if (heap.size() < k) { // 前k个数添加到小顶堆
                heap.add(data[i]); // logk
            } else if (data[i] > heap.front()) { // 如果是第k + 1个数，并且大于堆顶元素
                heap.replace(data[i]); // logk
            }
        }
        // O(nlogk)
        BinaryTrees.println(heap);
    }
}
